package com.example.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 面试题 08.07. 无重复字符串的排列组合
 * 无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
 * <p>
 * 示例1:
 * <p>
 * 输入：S = "qwe"
 * 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]
 * 示例2:
 * <p>
 * 输入：S = "ab"
 * 输出：["ab", "ba"]
 * <p>
 * 思路：全排列的变形，注意要求字串无重复字符，所以需要多一些操作
 */
public class Permutations2 {
    List<String> res = new ArrayList<>();
    String S;

    public String[] permutation(String S) {
        if (S.length() <= 1) return new String[]{S};
        this.S = S;
        back(new StringBuilder());
        String[] s = new String[res.size()];
        return res.toArray(s);
    }

    public void back(StringBuilder str) {
        if (str.length() == S.length()) {
            res.add(new String(str));
            return;
        }
        for (int i = 0; i < S.length(); i++) {
            if (str.toString().contains(S.charAt(i) + "")) {
                continue;
            }
            str.append(S.charAt(i));
            back(str);
            str.deleteCharAt(str.length() - 1);
        }
    }
}

